//  https://leetcode-cn.com/problems/merge-sorted-array
//  MergeSortedArray.swift
//  LeetCodeSwift
//
//  Created by XFB on 2019/7/30.
//  Copyright © 2019 XFB. All rights reserved.
//  合并两个有序数组

import Foundation

class MergeSortedArray {
    
    /**
     给定两个【有序】整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
     说明: 【***重点***】 m 和 n
     初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
     你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
     示例:
     输入:
     nums1 = [1,2,3,0,0,0], m = 3
     nums2 = [2,5,6],       n = 3
     
     输出: [1,2,2,3,5,6]
     */
    
    func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) -> [Int] {
        /// 双指针
        var i = m - 1
        var j = n - 1
        
        while i >= 0 || j >= 0 {

            if (j < 0 || (i >= 0 && nums1[i] > nums2[j])) {
                ///
                nums1[i + j + 1] = nums1[i]
                i = i - 1
            } else {
                nums1[i + j + 1] = nums2[j]
                j = j - 1
            }
        }
        return nums1
    }
    
}
